package arithmetic;

import utils.PrintUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Jie
 * @Date: 2019/3/7 11:20
 * 79
 * @Function :212
 */
public class A_19_TrieSearchWorld {
    public static void main(String[] args) {
        char[][] board = {
                {'o', 'a', 'a', 'n'},
                {'e', 't', 'a', 'e'},
                {'i', 'h', 'k', 'r'},
                {'i', 'f', 'l', 'v'}
        };
        String[] words = {"oath", "pea", "eat", "rain"};
        List<String> words1 = findWords(board, words);
        PrintUtil.print(words1);
    }

    //insert trie
    public static List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        Trie trie = new Trie();
        for (String str : words) {
            trie.insert(str);
        }
        //查找
        findWords(res, trie, board);
        return res;
    }

    //add trie
    private static void findWords(List<String> res, Trie trie, char[][] board) {

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                char c = board[i][j];
                if (trie.startsWith(String.valueOf(c))) {
                    find(i, j, trie, board, res, "", new boolean[board.length][board[i].length]);
                }
            }
        }
    }
    //find 上下左右
    private static void find(int i, int j, Trie trie, char[][] board, List<String> res, String str, boolean[][] isUsed) {
        //查找到，图形的边界。退出。
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length) return;
        if (isUsed[i][j]) return;//使用过，退出。

        //所有可以拼成的单词的可能。
        str = str + board[i][j];
        if (!trie.startsWith(str)) {
            return;
        }
        if (trie.search(str) && !res.contains(str)) {//当前单词。存在。
            res.add(str);
        }
        isUsed[i][j] = true;
        //上下左右
        //查找更长的单词
        find( i -1, j, trie, board, res, str, isUsed);
        find( i +1, j, trie, board, res, str, isUsed);
        find( i, j-1, trie, board, res, str, isUsed);
        find( i, j+1, trie, board, res, str, isUsed);
        //查找完，回退。
        isUsed[i][j] = false;
    }
}
